package sudoku.draft

import sudoku.support.*
import java.lang.RuntimeException

/**
 * @author flutterdash@qq.com
 * @since 2021/9/30 21:42
 */
fun main() {
    val original = getInput().print()
    println("*".repeat(22))
    resolve(original).print()
}

fun getInput(): Board = defaultTestBoard()

fun resolve(input: Board): Board {
    Cache.init(input)
    if (!core(input)) {
        throw RuntimeException("此数独无解")
    }
    return Cache.showAnswer()
}

fun core(board: Board, pos: Pos = Pos()): Boolean {
    if (pos.finished) return true

    if (board[pos.row][pos.col] == 0) {
        for (num in 1..9) {
            if (Cache.canUse(pos.row, pos.col, num)) {
                Cache.makeMark(pos.row, pos.col, num)
                if (core(board, pos.next()))
                    return true
                Cache.removeMark(pos.row, pos.col, num)
            }
        }
    } else {
        return core(board, pos.next())
    }

    return false
}

// struct

data class Pos(
    var row: Int = 0,
    var col: Int = 0
) {
    val finished: Boolean get() = (row == side)

    fun next(): Pos {
        val nextPos = this.copy()
        return if (col + 1 == side)
            nextPos.newline()
        else
            nextPos.apply {
                this@apply.col++
            }
    }

    private fun newline(): Pos {
        row++
        col = 0
        return this
    }

    private fun copy(): Pos = Pos(row, col)
}

object Cache {
    private var board: Board = emptyBoard()

    private val row = Array(side) { BooleanArray(10) { false } }
    private val col = Array(side) { BooleanArray(10) { false } }
    private val box = Array(3) {
        Array(3) {
            BooleanArray(10) { false }
        }
    }

    fun init(board: Board) {
        this.board = board.copy()
        for (r in board.indices) {
            for (c in board[r].indices) {
                if (board[r][c] in 1..9) {
                    makeMark(r, c, board[r][c])
                }
            }
        }
    }

    fun canUse(r: Int, c: Int, num: Int): Boolean {
        return !(row[r][num] || col[c][num] || box[r/3][c/3][num])
    }

    fun makeMark(r: Int, c: Int, num: Int) {
        board[r][c] = num
        row[r][num] = true
        col[c][num] = true
        box[r/3][c/3][num] = true
    }

    fun removeMark(r: Int, c: Int, num: Int) {
        board[r][c] = 0
        row[r][num] = false
        col[c][num] = false
        box[r/3][c/3][num] = false
    }

    fun showAnswer(): Board = this.board.copy()
}
